The present invention relates to a method for providing antialiasing to a computer displayed line. More specifically, the present invention pertains to a method applying barycentric coordinates for computing a normalized minor axis distance to an ideal line which can then be used as part of the antialiasing technique.
Today, computer graphics is used in a wide variety of applications, such as in business, science, animation, simulation, computer-aided design, process control, electronic publication, etc. Basically, computer generated graphics are comprised of points, lines, and polygons, which collectively are referred to as xe2x80x9cprimitives.xe2x80x9d These primitives are then rendered to display realistic two-dimensional and three-dimensional objects, images, and scenes. A complex three-dimensional scene may contain upwards of millions of such primitives.
The way by which primitives are rendered involves a scan conversion process. Basically, a computer screen is made up of millions of pixels (e.g., 980xc3x971024 monitor). The scan conversion process determines which pixels of a computer screen belong to which of the primitives. The pixels are then assigned attributes, such as color, depth, and blending, corresponding to the appropriate primitive. By way of example, FIG. 1 shows a small 5xc3x9711 array of pixels. Each individual pixel is represented, for purposes of illustration, as a square, and the pixel centers are represented as dots. A line can be represented by defining its endpoints. In FIG. 1, the vertices 110 and 111 define an ideal line 112. This straight horizontal line can be rendered for display by assigning a black color to pixels 101-109, while maintaining the other pixels in an unchanged white background color.
Unfortunately, complications arise if a line is slanted, such that it is not either perfectly horizontal or vertical. FIG. 2 shows a slanted line 203. The ideal line 203 is defined by its endpoints which have vertices at 201 and 202. Ideal line 203 passes through pixels 204-216; assigning a black color to these pixels will produce the desired slanted line. However, as can be seen, the resulting line has a xe2x80x9cstair-steppedxe2x80x9d or xe2x80x9cjaggedxe2x80x9d appearance. Due to the aliases, the displayed line is not smooth and is visually unappealing. The effect of aliasing with respect to lines is particularly disturbing in scenes involving movement. Aliased lines appear to be scintillating.
In order to minimize the effects of line aliasing, designers have implemented a number of clever and useful antialiasing techniques. Antialiasing techniques typically blend the pixel as a function of coverage. Those pixel centers located further away from the ideal line are blended with the background color such that the line color has less effect than those pixels whose centers are closer to the ideal line. Essentially, the greater the pixel area covered by the line, the greater the line""s attribute contributes to that particular pixel. Referring back to the example shown in FIG. 2, the center of pixel 206 is relatively far away from ideal line 203. This means that the area of pixel 206 covered by ideal line 203 is relatively small. The final color value assigned to pixel 206 is a blended function of the line color and the background color. But because of the relatively small coverage value, the background color is assigned a higher weighting than that of the line color. Consequently, the final color for pixel 206 is closer to that of the background color than the line color. In contrast, the center of pixel 207 is extremely close to that of ideal line 203. This indicates that the area of pixel 207 covered by line 203 is relatively quite large (e.g. 50%). Thus, the line color is assigned a higher weighting than that of the background color for pixel 207. By way of example, given a white background and a black line, pixel 206 would have a very light gray color, whereas pixel 207 would have a much darker gray color. Rather than having a pixel be either black or white, the anti-aliasing technique assigns varying degrees of black, gray, and white. By blending an interpolated line color with the background color, a smoother, straighter, and more realistic display is produced.
Although these types of anti-aliasing techniques are quite effective, they are computationally expensive. For each pixel, the minor axis distance must be calculated, and the coverage must be determined before blending can occur. Calculating the minor axis distance for each sample point as the line is traversed typically entails computing an initial value for the first sample point, forward biasing this value as the line is traversed through linear interpolation, and performing difference calculations to determine the current sample point with respect to the ideal line. These calculations consume valuable time and processing resources. As such, some computers become overwhelmed and are simply incapable of handling high-quality antialiasing for complex, three-dimensional scenes, especially those involving real-time, interactive graphics. Furthermore, antialiasing techniques become even more problematic for lines which are thicker than one pixel wide. It can be difficult to adapt standard antialiasing techniques to these variable width lines.
Thus, there exists a need for a system and method which can readily and accurately calculate the minor axis distance from a sample point to an ideal line for purposes of facilitating antialiasing. It would be preferable if such a system and method were to generate normalized distances so that standard anti-aliasing techniques are readily adapted to handle variable width lines. The present invention provides a novel solution which meets the above needs and which is computationally inexpensive.
The present invention pertains to a method for applying the principles of barycentric coordinates to perform antialiasing for a computer generated line. A line is defined by its two endpoints. In the present invention, a third point is specified for the purpose of forming a triangle defined by the two endpoints and the third point. Thereby, subarea computations can be performed for any pixel sample point relative to this triangle in order to generate barycentric coordinates which uniquely define that particular sample point. The three barycentric coordinates corresponding to the triangle are then mapped to create two barycentric coordinates, one for each of the two endpoints. An interpolated pixel color can be calculated as a function of these two barycentric coordinates applied to the color of the pixels corresponding to the two endpoints. One of the barycentric coordinates gives the relative minor axis distance from the sample point to the line. This barycentric coordinate is used as an index into a table containing pre-computed coverage values. The appropriate coverage value is then used to modulate a blending value, alpha. The interpolated pixel color is then blended with the background color according to the alpha value.